CSE408
Vertex Cover and Bin
Packing
Lecture # 37
The vertex-cover problem
Example
The set cover problem
Set cover algo
Bin Packing
• In the bin packing problem, objects of different volumes must
be packed into a finite number of bins or containers each of
volume V in a way that minimizes the number of bins used. In
computational complexity theory, it is a combinatorial NP-
hard problem.
• There are many variations of this problem, such as 2D
packing, linear packing, packing by weight, packing by cost,
and so on.
• They have many applications, such as filling up containers,
loading trucks with weight capacity constraints, creating file
backups in removable media and technology mapping in
Field-programmable gate array semiconductor chip design.
➢ The bin packing problem can also be seen as a special case of the cutting
stock problem.
➢ When the number of bins is restricted to 1 and each item is characterised
by both a volume and a value, the problem of maximising the value of
items that can fit in the bin is known as the knapsack problem.
➢ Despite the fact that the bin packing problem has an NP-hard
computational complexity, optimal solutions to very large instances of the
problem can be produced with sophisticated algorithms.
➢ In addition, many heuristics have been developed: for example, the first fit
algorithm provides a fast but often non-optimal solution, involving placing
each item into the first bin in which it will fit.
➢ It requires Θ(n log n) time, where n is the number of elements to be
packed.
Bin packing
• The algorithm can be made much more effective by first
sorting the list of elements into decreasing order
(sometimes known as the first-fit decreasing algorithm),
although this still does not guarantee an optimal solution,
and for longer lists may increase the running time of the
algorithm.
• It is known, however, that there always exists at least one
ordering of items that allows first-fit to produce an optimal
solution.
[1]
• An interesting variant of bin packing that occurs in practice
is when items can share space when packed into a bin.
• Specifically, a set of items could occupy less space when
packed together than the sum of their individual sizes.
• This variant is known as VM packing
[2]
since when
virtual machines (VMs) are packed in a server,
their total memory requirement could decrease
due to pages shared by the VMs that need only
be stored once.
• If items can share space in arbitrary ways, the bin
packing problem is hard to even approximate.
• However, if the space sharing fits into a hierarchy,
as is the case with memory sharing in virtual
machines, the bin packing problem can be
efficiently approximated.
CSE408
Modular Arithmetic &
Chinese Remainder
Theorem
Lecture # 38
Modular Arthmetic
• Modular arithmetic can be handled mathematically by
introducing a congruence relation on the integers that is
compatible with the operations of the ring of integers:
addition, subtraction, and multiplication. For a positive
integer n, two integers a and b are said to be congruent
modulo n, written:
• if their difference a − b is an integer multiple of n (or n
divides a − b). The number n is called the modulus of the
congruence.
• The properties that make this relation a congruence relation
(respecting addition, subtraction, and multiplication) are the
following.
• If
• And
• then:
• It should be noted that the above two properties would
still hold if the theory were expanded to include all real
numbers, that is if were not necessarily all integers. The
next property, however, would fail if these variables were
not all integers:
Chinese Theorem
• The Chinese remainder theorem is a result about congruences in
number theory and its generalizations in abstract algebra. It was
first published in the 3rd to 5th centuries by Chinese mathematician
Sun Tzu.
• In its basic form, the Chinese remainder theorem will determine a
number n that when divided by some given divisors leaves given
remainders.
• For example, what is the lowest number n that when divided by 3
leaves a remainder of 2, when divided by 5 leaves a remainder of 3,
and when divided by 7 leaves a remainder of 2?
• A common introductory example is a woman who tells a policeman
that she lost her basket of eggs, and that if she makes three
portions at a time out of it, she was left with 2, if she makes five
portions at a time out of it, she was left with 3, and if she makes
seven portions at a time out of it, she was left with 2.
• She then asks the policeman what is the minimum number of eggs
she must have had. The answer to both problems is 23.
Example
Brute Force Technique:-
CSE408
GCD and
Optimization Problem
Lecture # 39
L11
2
Euclidean Algorithm
m , n gcd(m,n)
integer euclid(pos. integer m, pos. integer n)
x = m, y = n
while(y > 0)
r = x mod y
x = y
y = r
return x
Euclidean
Algorithm
L11
3
Euclidean Algorithm. Example
gcd(33,77):
Step
r = x
mod
y x y
0
-
33 77
L11
4
gcd(33,77):
Step
r = x
mod
y x y
0
-
33 77
1
33 mod 77
= 33
77 33
Euclidean Algorithm. Example
L11
5
gcd(33,77):
Step
r = x
mod
y x y
0
-
33 77
1
33 mod 77
= 33
77 33
2
77 mod 33
= 11
33 11
Euclidean Algorithm. Example
L11
6
gcd(33,77):
Step
r = x
mod
y x y
0
-
33 77
1
33 mod 77
= 33
77 33
2
77 mod 33
= 11
33 11
3
33 mod 11
= 0
11 0
Euclidean Algorithm. Example
L11
7
gcd(244,117):
Step
r = x
mod
y x y
0
-
244 117
Euclidean Algorithm. Example
L11
8
gcd(244,117):
Step
r = x
mod
y x y
0
-
244 117
1 244 mod 117 = 10 117 10
Euclidean Algorithm. Example
L11
9
gcd(244,117):
Step
r = x
mod
y x y
0
-
244 117
1 244 mod 117 = 10 117 10
2 117 mod 10 = 7 10 7
Euclidean Algorithm. Example
L11
10
gcd(244,117):
Step
r = x
mod
y x y
0
-
244 117
1 244 mod 117 = 10 117 10
2 117 mod 10 = 7 10 7
3 10 mod 7 = 3 7 3
Euclidean Algorithm. Example
L11
11
gcd(244,117):
Step
r = x
mod
y x y
0
-
244 117
1 244 mod 117 = 10 117 10
2 117 mod 10 = 7 10 7
3 10 mod 7 = 3 7 3
4 7 mod 3 = 1 3 1
Euclidean Algorithm. Example
L11
12
gcd(244,117):
By definition ➔ 244 and 117 are rel. prime.
Step
r = x
mod
y x y
0
-
244 117
1 244 mod 117 = 10 117 10
2 117 mod 10 = 7 10 7
3 10 mod 7 = 3 7 3
4 7 mod 3 = 1 3 1
5 3 mod 1=0 1 0
Euclidean Algorithm. Example
L11
13
Euclidean Algorithm Correctness
The reason that Euclidean algorithm works is
gcd(x,y ) is not changed from line to line. If x’,
y’ denote the next values of x , y then:
gcd(x’,y’) = gcd(y, x mod y)
= gcd(y, x + qy) (the useful fact)
= gcd(y, x ) (subtract y -multiple)
= gcd(x,y)
Optimization Problem
• In mathematics and computer science, an optimization
problem is the problem of finding the best solution
from all feasible solutions. Optimization problems can
be divided into two categories depending on whether
the variables are continuous or discrete.
• An optimization problem with discrete variables is
known as a combinatorial optimization problem. In a
combinatorial optimization problem, we are looking for
an object such as an integer, permutation or graph
from a finite (or possibly countable infinite) set.
CSE408
Complexity Classes
Lecture # 40
NP-Completeness
• Poly time algorithm: input size n (in some
encoding), worst case running time – O(n
c
) for
some constant c.
• Three classes of problems
– P: problems solvable in poly time.
– NP: problems verifiable in poly time.
– NPC: problems in NP and as hard as any problem
in NP.
NP-Completeness (verifiable)
• Verifiable in poly time: given a certificate of a
solution, could verify the certificate is correct in
poly time.
• Examples (their definitions come later):
– Hamiltonian-cycle, given a certificate of a sequence
(v
1
,v
2
,…, v
n
), easily verified in poly time.
– 3-CNF, given a certificate of an assignment 0s, 1s,
easily verified in poly time.
– (so try each instance, and verify it, but 2
n
instances)
• Why not defined as “solvable in exponential
time?” or “Non Poly time”?
NP-Completeness (why NPC?)
• A problem p NP, and any other problem p
NP can be translated as p in poly time.
• So if p can be solved in poly time, then all
problems in NP can be solved in poly time.
• All current known NP hard problems have been
proved to be NPC.
Relation among P, NP, NPC
• P NP (Sure)
• NPC NP (sure)
• P = NP (or P NP, or P NP) ???
• NPC = NP (or NPC NP, or NPC NP) ???
• P NP: one of the deepest, most perplexing
open research problems in (theoretical)
computer science since 1971.
Arguments about P, NP, NPC
• No poly algorithm found for any NPC problem
(even so many NPC problems)
• No proof that a poly algorithm cannot exist for
any of NPC problems, (even having tried so
long so hard).
• Most theoretical computer scientists believe
that NPC is intractable (i.e., hard, and P NP).
View of Theoretical Computer Scientists on P, NP, NPC
NPC
P
NP
P NP, NPC NP, P NPC =
Why discussion on NPC
• If a problem is proved to be NPC, a good evidence for
its intractability (hardness).
• Not waste time on trying to find efficient algorithm
for it
• Instead, focus on design approximate algorithm or a
solution for a special case of the problem
• Some problems looks very easy on the surface, but in
fact, is hard (NPC).
Decision VS. Optimization Problems
• Decision problem: solving the problem by giving an
answer “YES” or “NO”
• Optimization problem: solving the problem by
finding the optimal solution.
• Examples:
– SHORTEST-PATH (optimization)
• Given G, u,v, find a path from u to v with fewest edges.
– PATH (decision)
• Given G, u,v, and k, whether exist a path from u to v consisting of
at most k edges.
Decision VS. Optimization Problems (Cont.)
• Decision is easier (i.e., no harder) than optimization
• If there is an algorithm for an optimization problem,
the algorithm can be used to solve the
corresponding decision problem.
– Example: SHORTEST-PATH for PATH
• If optimization is easy, its corresponding decision is
also easy. Or in another way, if provide evidence that
decision problem is hard, then the corresponding
optimization problem is also hard.
• NPC is confined to decision problem. (also
applicable to optimization problem.)
– Another reason is that: easy to define reduction between
decision problems.
(Poly) reduction between decision problems
• Problem (class) and problem instance
• Instance of decision problem A and instance
of decision problem B
• A reduction from A to B is a transformation
with the following properties:
– The transformation takes poly time
– The answer is the same (the answer for is YES if
and only if the answer for is YES).
Implication of (poly) reduction
(Poly) Reduction Algorithm for B
Decision algorithm for A
1. If decision algorithm for B is poly, so does A.
A is no harder than B (or B is no easier than A)
2. If A is hard (e.g., NPC), so does B.
3. How to prove a problem B to be NPC ??
3.1 find a already proved NPC problem A
3.2 establish an (poly) reduction from A to B
Question: What is and how to prove the first NPC problem?
Circuit-satisfiability problem.
(at first, prove B is in NP, which is generally easy.)
Discussion on Poly time problems
• (n
100
) vs. (2
n
)
– Reasonable to regard a problem of (n
100
) as
intractable, however, very few practical problem with
(n
100
).
– Most poly time algorithms require much less.
– Once a poly time algorithm is found, more efficient
algorithm may follow soon.
• Poly time keeps same in many different
computation models, e.g., poly class of serial
random-access machine poly class of abstract
Turing machine poly class of parallel computer
(#processors grows polynomially with input size)
• Poly time problems have nice closure properties
under addition, multiplication and composition.
Encoding impact on complexity
• The problem instance must be represented in a way
the program (or machine) can understand.
• General encoding is “binary representation”.
• Different encoding will result in different
complexities.
• Example: an algorithm, only input is integer k,
running time is (k).
– If k is represented in unary: a string of k 1s, the running
time is (k) = (n) on length-n input, poly on n.
– If k is represented in binary: the input length n = log k
+1, the running time is (k) = (2
n
), exponential on n.
• Ruling out unary, other encoding methods are same.
Examples of encoding and complexity
• Given integer n, check whether n is a
composite.
• Dynamic programming for subset-sum.
Class P Problems
• Let n= the length of binary encoding of a problem
(i.e., input size), T(n) is the time to solve it.
• A problem is poly-time solvable if T(n) =O(n
k
) for
some constant k.
• Complexity class P=set of problems that are poly-
time solvable.
Poly Time Verification
• PATH problem: Given <G,u,v,k>, whether
exists a path from u to v with at most k
edges?
• Moreover, also given a path p from u to v,
verify whether the length of p is at most k?
• Easy or not?
Of course, very easy.
Poly Time Verification, encoding, and language
• Hamiltonian cycles
– A simple path containing every vertex.
– HAM-CYCLE={<G>: G is a Hamiltonian graph, i.e. containing
Hamiltonian cycle}.
– Suppose n is the length of encoding of G.
– HAM-CYCLE can be considered as a Language after encoding, i.e. a
subset of * where ={0,1}*.
• The naïve algorithm for determining HAM-CYCLE runs in
(m!)=(2
m
) time, where m is the number of vertices, m
n
1/2
.
• However, given an ordered sequence of m vertices (called
“certificate”), let you verify whether the sequence is a
Hamiltonian cycle. Very easy. In O(n
2
) time.
Class NP problems
• For a problem p, given its certificate, the
certificate can be verified in poly time.
• Call this kind of problem an NP one.
• Complement set/class: Co-NP.
– Given a set S (as a universal) and given a subset A
– The complement is that S-A.
– When NP problems are represented as languages
(i.e. a set), we can discuss their complement set,
i.e., Co-NP.
Relation among P, NP and co-NP={L: L NP where L= *-L}
P
P
NP-completeness and Reducibility
• A (class of) problem P
1
is poly-time reducible to
P
2
, written as P
1
p
P
2
if there exists a poly-time
function f: P
1
→ P
2
such that for any instance of
p
1
P
1
, p
1
has “YES” answer if and only if answer
to f(p
1
) ( P
2
) is also “YES”.
• Theorem 34.3: (page 985)
– For two problems P
1
, P
2
, if P
1
p
P
2
then P
2
P implies
P
1
P.
NP-completeness and Reducibility (cont.)
• A problem p is NP-complete if
1. p NP and
2. p'
p
p for every p' NP.
(if p satisfies 2, then p is said NP-hard.)
Theorem 34.4 (page 986)
if any NP-compete problem is poly-time
solvable, then P=NP. Or say: if any problem in
NP is not poly-time solvable, then no NP-
complete problem is poly-time solvable.
First NP-complete problem—Circuit
Satisfiability (problem definition)
• Boolean combinational circuit
– Boolean combinational elements, wired together
– Each element, inputs and outputs (binary)
– Limit the number of outputs to 1.
– Called logic gates: NOT gate, AND gate, OR gate.
– true table: giving the outputs for each setting of inputs
– true assignment: a set of boolean inputs.
– satisfying assignment: a true assignment causing the output
to be 1.
– A circuit is satisfiable if it has a satisfying assignment.
Circuit Satisfiability Problem: definition
• Circuit satisfying problem: given a boolean
combinational circuit composed of AND, OR, and
NOT, is it stisfiable?
• CIRCUIT-SAT={<C>: C is a satisfiable boolean circuit}
• Implication: in the area of computer-aided hardware
optimization, if a subcircuit always produces 0, then
the subcircuit can be replaced by a simpler subcircuit
that omits all gates and just output a 0.
Two instances of circuit satisfiability problems
Solving circuit-satisfiability problem
• Intuitive solution:
– for each possible assignment, check whether it
generates 1.
– suppose the number of inputs is k, then the
total possible assignments are 2
k
. So the
running time is (2
k
). When the size of the
problem is (k), then the running time is not
poly.
Circuit-satisfiability problem is NP-
complete
• Lemma 34.5:(page 990)
– CIRCUIT-SAT belongs to NP.
• Proof: CIRCUIT-SAT is poly-time verifiable.
– Given (an encoding of) a CIRCUIT-SAT problem C and a certificate,
which is an assignment of boolean values to (all) wires in C.
– The algorithm is constructed as follows: just checks each gates and
then the output wire of C:
• If for every gate, the computed output value matches the value of the
output wire given in the certificate and the output of the whole circuit
is 1, then the algorithm outputs 1, otherwise 0.
• The algorithm is executed in poly time (even linear time).
• An alternative certificate: a true assignment to the inputs.
Circuit-satisfiability problem is NP-
complete (cont.)
• Lemma 34.6: (page 991)
– CIRCUIT-SAT is NP-hard.
• Proof: Suppose X is any problem in NP
– construct a poly-time algorithm F maps every
problem instance x in X to a circuit C=f(x) such that
the answer to x is YES if and only if CCIRCUIT-SAT
(is satisfiable).
Circuit-satisfiability problem is NP-hard (cont.)
• Since XNP, there is a poly-time algorithm A
which verifies X.
• Suppose the input length is n and Let T(n)
denote the worst-case running time. Let k be
the constant such that T(n)=O(n
k
) and the
length of the certificate is O(n
k
).
Circuit-satisfiability problem is NP-hard (cont.)
• Idea is to represent the computation of A as a
sequence of configurations, c
0
, c
1
,…,c
i
,c
i+1
,…,c
T(n)
,
each c
i
can be broken into
– (program for A, program counter PC, auxiliary machine state, input x,
certificate y, working storage) and
– c
i
is mapped to c
i+1
by the combinational circuit M
implementing the computer hardware.
– The output of A: 0 or 1– is written to some designated
location in working storage. If the algorithm runs for at
most T(n) steps, the output appears as one bit in c
T(n)
.
– Note: A(x,y)=1 or 0.
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Circuit-satisfiability problem is NP-hard (cont.)
• The reduction algorithm F constructs a single
combinational circuit C as follows:
– Paste together all T(n) copies of the circuit M.
– The output of the ith circuit, which produces c
i
, is directly
fed into the input of the (i+1)st circuit.
– All items in the initial configuration, except the bits
corresponding to certificate y, are wired directly to their
known values.
– The bits corresponding to y are the inputs to C.
– All the outputs to the circuit are ignored, except the one
bit of c
T(n)
corresponding to the output of A.
Circuit-satisfiability problem is NP-hard (cont.)
• Two properties remain to be proven:
– F correctly constructs the reduction, i.e., C is
satisfiable if and only if there exists a certificate y,
such that A(x,y)=1.
Suppose there is a certificate y, such that A(x,y)=1. Then
if we apply the bits of y to the inputs of C, the output of
C is the bit of A(x,y), that is C(y)= A(x,y) =1, so C is
satisfiable.
Suppose C is satisfiable, then there is a y such that
C(y)=1. So, A(x,y)=1.
– F runs in poly time.
Circuit-satisfiability problem is NP-hard (cont.)
– F runs in poly time.
• Poly space:
– Size of x is n.
– Size of A is constant, independent of x.
– Size of y is O(n
k
).
– Amount of working storage is poly in n since A runs at most O(n
k
).
– M has size poly in length of configuration, which is poly in O(n
k
), and
hence is poly in n.
– C consists of at most O(n
k
) copies of M, and hence is poly in n.
– Thus, the C has poly space.
• The construction of C takes at most O(n
k
) steps and each step takes
poly time, so F takes poly time to construct C from x.
CIRCUIT-SAT is NP-complete
• In summary
– CIRCUIT-SAT belongs to NP, verifiable in poly time.
– CIRCUIT-SAT is NP-hard, every NP problem can be
reduced to CIRCUIT-SAT in poly time.
– Thus CIRCUIT-SAT is NP-complete.
NP-completeness proof basis
• Lemma 34.8 (page 995)
– If X is a problem (class) such that P'
p
X for some P'
NPC, then X is NP-hard. Moreover, if X NP, then X
NPC.
• Steps to prove X is NP-complete
– Prove X NP.
• Given a certificate, the certificate can be verified in poly time.
– Prove X is NP-hard.
• Select a known NP-complete P'.
• Describe a transformation function f that maps every instance x
of P' into an instance f(x) of X.
• Prove f satisfies that the answer to xP' is YES if and only if the
answer to f(x)X is YES for all instance x P'.
• Prove that the algorithm computing f runs in poly-time.
NPC proof –Formula Satisfiability (SAT)
• SAT definition
– n boolean variables: x
1
, x
2
,…, x
n
.
– M boolean connectives: any boolean function with one
or two inputs and one output, such as ,,,→,,…
and
– Parentheses.
• A SAT is satisfiable if there exists an true
assignment which causes to evaluate to 1.
• SAT={< >: is a satifiable boolean formula}.
• The historical honor of the first NP-complete
problem ever shown.
SAT is NP-complete
• Theorem 34.9: (page 997)
– SAT is NP-complete.
• Proof:
– SAT belongs to NP.
• Given a satisfying assignment, the verifying algorithm
replaces each variable with its value and evaluates the
formula, in poly time.
– SAT is NP-hard (show CIRCUIT-SAT
p
SAT).
SAT is NP-complete (cont.)
• CIRCUIT-SAT
p
SAT, i.e., any instance of circuit
satisfiability can be reduced in poly time to an instance
of formula satisfiability.
• Intuitive induction:
– Look at the gate that produces the circuit output.
– Inductively express each of gate’s inputs as formulas.
– Formula for the circuit is then obtained by writing an
expression that applies the gate’s function to its input
formulas.
•Unfortunately, this is not a poly reduction
–Shared formula (the gate whose output is fed to 2 or more inputs of
other gates) cause the size of generated formula to grow exponentially.
SAT is NP-complete (cont.)
• Correct reduction:
– For every wire x
i
of C, give a variable x
i
in the formula.
– Every gate can be expressed as x
o
(x
i
1
x
i
2
… x
i
l
)
– The final formula is the AND of the circuit output variable
and conjunction of all clauses describing the operation of
each gate. (example Figure 34.10)
• Correctness of the reduction
– Clearly the reduction can be done in poly time.
– C is satisfiable if and only if is satisfiable.
• If C is satisfiable, then there is a satisfying assignment. This means
that each wire of C has a well-defined value and the output of C is 1.
Thus the assignment of wire values to variables in makes each
clause in evaluate to 1. So is 1.
• The reverse proof can be done in the same way.
Example of reduction of CIRCUIT-SAT to SAT
= x
10
(x
10
(x
7
x
8
x
9
))
(x
9
(x
6
x
7
))
(x
8
(x
5
x
6
))
(x
7
(x
1
x
2
x
4
))
(x
6
x
4
))
(x
5
(x
1
x
2
))
(x
4
x
3
)
INCORRECT REDUCTION: = x
10
= x
7
x
8
x
9
=(x
1
x
2
x
4
) (x
5
x
6
) (x
6
x
7
)
=(x
1
x
2
x
4
) ((x
1
x
2
) x
4
) (x
4
(x
1
x
2
x
4
))=….
NPC Proof –3-CNF Satisfiability
• 3-CNF definition
– A literal in a boolean formula is an occurrence of a variable
or its negation.
– CNF (Conjunctive Nornal Form) is a boolean formula
expressed as AND of clauses, each of which is the OR of
one or more literals.
– 3-CNF is a CNF in which each clause has exactly 3 distinct
literals (a literal and its negation are distinct)
• 3-CNF-SAT: whether a given 3-CNF is satiafiable?
3-CNF-SAT is NP-complete
• Proof: 3-CNF-SAT NP. Easy.
– 3-CNF-SAT is NP-hard. (show SAT
p
3-CNF-SAT)
• Suppose is any boolean formula, Construct a binary ‘parse’ tree,
with literals as leaves and connectives as internal nodes.
• Introduce a variable y
i
for the output of each internal nodes.
• Rewrite the formula to ' as the AND of the root variable and a
conjunction of clauses describing the operation of each node.
• The result is that in ', each clause has at most three literals.
• Change each clause into conjunctive normal form as follows:
– Construct a true table, (small, at most 8 by 4)
– Write the disjunctive normal form for all true-table items evaluating to 0
– Using DeMorgan law to change to CNF.
• The resulting '' is in CNF but each clause has 3 or less literals.
• Change 1 or 2-literal clause into 3-literal clause as follows:
– If a clause has one literal l, change it to (lpq)(lpq) (lpq)
(lpq).
– If a clause has two literals (l
1
l
2
), change it to (l
1
l
2
p) (l
1
l
2
p).
Binary parse tree for =((x
1
→ x
2
) ((x
1
x
3
) x
4
))x
2
'= y
1
(y
1
(y
2
x
2
))
(y
2
(y
3
y
4
))
(y
4
y
5
)
(y
3
(x
1
→ x
2
))
(y
5
(y
6
x
4
))
(y
6
(x
1
x
3
))
Example of Converting a 3-literal clause to CNF format
Disjunctive Normal Form:
i
'=(y
1
y
2
x
2
)(y
1
y
2
x
2
)
(y
1
y
2
x
2
) (y
1
y
2
x
2
)
Conjunctive Normal Form:
i
''=(y
1
y
2
x
2
)(y
1
y
2
x
2
)
(y
1
y
2
x
2
)(y
1
y
2
x
2
)
3-CNF is NP-complete
• and reduced 3-CNF are equivalent:
– From to ' , keep equivalence.
– From ' to '' , keep equivalence.
– From '' to final 3-CNF, keep equivalence.
• Reduction is in poly time,
– From to ' , introduce at most 1 variable and 1 clause per
connective in .
– From ' to '' , introduce at most 8 clauses for each clause in '.
– From '' to final 3-CNF, introduce at most 4 clauses for each clause in
''.
NP-completeness proof structure
NPC proof -- CLIQUE
• Definition: a clique in an undirected graph G=(V,E) is a
subset V'V of vertices, each pair of which is connected
by an edge in E, i.e., a clique is a complete subgraph of G.
• Size of a clique is the number of vertices in the clique.
• Optimization problem: find the maximum clique.
• Decision problem: whether a clique of given size k exists
in the graph?
• CLIQUE={<G,k>: G is a graph with a clique of size k.}
• Intuitive solution: ???
CLIQUE is NP-complete
• Theorem 34.11: (page 1003)
– CLIQUE problem is NP-complete.
• Proof:
– CLIUEQE NP: given G=(V,E) and a set V'V as a
certificate for G. The verifying algorithm checks for
each pair of u,vV', whether <u,v> E. time:
O(|V'|
2
|E|).
– CLIQUE is NP-hard:
• show 3-CNF-SAT
p
CLUQUE.
• The result is surprising, since from boolean formula to
graph.
CLIQUE is NP-complete
• Reduction from 3-CNF-SAT to CLUQUE.
– Suppose =C
1
C
2
… C
k
be a boolean formula in 3-CNF
with k clauses.
– We construct a graph G=(V,E) as follows:
• For each clause C
r
=(l
1
r
l
2
r
l
3
r
), place a triple of v
1
r
, v
2
r
, v
3
r
into V
• Put the edge between two vertices v
i
r
and v
j
s
when:
– rs, that is v
i
r
and v
j
s
are in different triples, and
– Their corresponding literals are consistent, i.e, l
i
r
is not negation of l
j
s
.
– Then is satisfiable if and only if G has a clique of size k.
=(x
1
x
2
x
3
)(x
1
x
2
x
3
)(x
1
x
2
x
3
) and its reduced graph G
C
1
=x
1
x
2
x
3
CLIQUE is NP-complete
• Prove the above reduction is correct:
– If is satisfiable, then there exists a satisfying assignment,
which makes at least one literal in each clause to evaluate to
1. Pick one this kind of literal in each clause. Then consider
the subgraph V' consisting of the corresponding vertex of
each such literal. For each pair v
i
r
,v
j
s
V', where rs. Since
l
i
r
,l
j
s
are both evaluated to 1, so l
i
r
is not negation of l
j
s
, thus
there is an edge between v
i
r
and v
j
s
. So V' is a clique of size k.
– If G has a clique V' of size k, then V' contains exact one
vertex from each triple. Assign all the literals corresponding
to the vertices in V' to 1, and other literals to 1 or 0, then
each clause will be evaluated to 1. So is satisfiable.
• It is easy to see the reduction is in poly time.
• The reduction of an instance of one problem to a
specific instance of the other problem.
Traveling-salesman problem is NPC
• TSP={<G,c,k>:
G=(V,E) is a complete graph,
c is a function from VV→Z,
kZ, and G has a traveling salesman
tour with cost at most k.}
• Theorem 34.14: (page 1012)
– TSP is NP-complete.
TSP is NP-complete
• TSP belongs to NP:
– Given a certificate of a sequence of vertices in the tour, the
verifying algorithm checks whether each vertex appears once,
sums up the cost and checks whether at most k. in poly time.
• TSP is NP-hard (show HAM-CYCLE
p
TSP)
– Given an instance G=(V,E) of HAM-CYCLE, construct a TSP
instance <G',c,0) as follows (in poly time):
• G'=(V,E'), where E'={<i,j>: i,j V and ij} and
• Cost function c is defined as c(i,j)=0 if (i,j) E, 1, otherwise.
– If G has a hamiltonian cycle h, then h is also a tour in G' with
cost at most 0.
– If G' has a tour h' of cost at most 0, then each edge in h' is 0, so
each edge belong to E, so h' is also a hilmitonian cycle in G.
Subset Sum is NPC
• SUNSET-SUM={<S,t>: S is a set of integers
and there exists a S'S such that t=
sS'
s.}
• Theorem 34.15: (page 1014)
– SUBSET-SUM is NP-complete.
SUBSET-SUM is NPC
• SUBSET-SUM belongs to NP.
– Given a certificate S', check whether t is sum of
S' can be finished in poly time.
• SUBSET-SUM is NP-hard (show 3-CNF-
SAT
p
SUBSET-SUM).
SUBSET-SUM is NPC
• Given a 3-CNF formula =C
1
C
2
… C
k
with literals x
1
, x
2
,…, x
n
. Construct a SUBSET-
SUM instance as follows:
– Two assumptions: no clause contains both a literal and its negation, and either a literal or
its negation appears in at least one clause.
– The numbers in S are based on 10 and have n+k digits, each digit corresponds to (or is
labeled by) a literal or a clause.
– Target t=1…1||4…4 (n 1’s and k 4’s)
– For each literal x
i
, create two integers:
• v
i
=0…01
(i)
0…0||0…01
(l)
0…01
(w)
0…0, where x
i
appears in C
l
,…,C
w.
• v
i
'=0…01
(i)
0…0||0…1
(m)
0……01
(p)
0…0, where x
i
appears in C
m
,…,C
p.
.
• Clearly, v
i
and v
i
' can not be equal in right k digits, moreover all v
i
and v
i
' in S are distinct.
– For each clause C
j
, create two integers:
• s
j
=0…0||0…01
(j)
0…0,
• s
j
'=0…0||0…02
(j)
0…0.
• all s
j
and s
j
' are called “slack number”. Clearly, all s
j
and s
j
' in S are distinct.
– Note: the sum of digits in any one digit position is 2 or 6, so when there is no carries when adding any
subset of the above integers.
SUBSET-SUM is NPC
• The above reduction is done in poly time.
• The 3-CNF formula is satisfiable if and only if there is a subset S'
whose sum is t.
– suppose has a satisfying assignment.
• Then for i=1,…,n, if x
i
=1 in the assignment, then v
i
is put in S', otherwise, then
v
i
' is put in S'.
• The digits labeled by literals will sum to 1.
• Moreover, for each digit labeled by a clause C
j
and in its three literals, there
may be 1, 2, or 3 assignments to be 1. correspondingly, both s
j
and s
j
' or s
j
', or
s
j
is added to S' to make the sum of the digit to 4.
• So S' will sum to 1…14…4.
– Suppose there is a S' which sums to 1…14…4. then S' contains exact one
of v
i
and v
i
' for i=1,…,n. if v
i
S', then set x
i
=1, otherwise, v
i
' S', then set
x
i
=0. It can be seen that this assignment makes each clause of to
evaluate to 1. so is satisfiable.
Master Theorem:
Practice Problems a nd Solutions
Master Theorem
The Master Theorem applies to recurrences of the following form:
T (n) = aT (n/b) + f (n)
where a ≥ 1 and b > 1 are constants and f (n) is an asymptotically positive function.
There are 3 cases:
1. If f(n) = O(n
log
b
a−
) for some constant > 0, then T (n) = Θ(n
log
b
a
).
2. If f(n) = Θ(n
log
b
a
log
k
n) with
1
k ≥ 0, then T (n) = Θ(n
log
b
a
log
k+1
n).
3. If f(n) = Ω(n
log
b
a+
) with > 0, and f(n) satisfies the re gularity c ondition, then T (n) = Θ(f(n)).
Regularity condition: af(n/b) ≤ c f (n) for some constant c < 1 and all sufficiently la rge n.
Practice Problems
For each of the following recurrences, give an expression for the runtime T (n) if the recurrence can be
solved with the Master Theorem. Otherwise, indicate that the Master Theor e m does not apply.
1. T (n) = 3T (n/2) + n
2
2. T (n) = 4T (n/2) + n
2
3. T (n) = T (n/2) + 2
n
4. T (n) = 2
n
T (n/2) + n
n
5. T (n) = 16T (n/4) + n
6. T (n) = 2T (n/2) + n log n
1
most of the time, k = 0
1
7. T (n) = 2T (n/2) + n/ log n
8. T (n) = 2T (n/4) + n
0.51
9. T (n) = 0.5T (n/2) + 1/n
10. T (n) = 16T (n/4) + n!
11. T (n) =
√
2T (n/2) + log n
12. T (n) = 3T (n/ 2) + n
13. T (n) = 3T (n/ 3) +
√
n
14. T (n) = 4T (n/ 2) + cn
15. T (n) = 3T (n/ 4) + n log n
16. T (n) = 3T (n/ 3) + n/2
17. T (n) = 6T (n/ 3) + n
2
log n
18. T (n) = 4T (n/ 2) + n/ log n
19. T (n) = 64T (n/8) − n
2
log n
20. T (n) = 7T (n/ 3) + n
2
21. T (n) = 4T (n/ 2) + log n
22. T (n) = T (n/2 ) + n(2 − cos n)
2
Solutions
1. T (n) = 3T (n/2) + n
2
=⇒ T (n) = Θ(n
2
) (Case 3)
2. T (n) = 4T (n/2) + n
2
=⇒ T (n) = Θ(n
2
log n) (Case 2)
3. T (n) = T (n/2) + 2
n
=⇒ Θ(2
n
) (Case 3)
4. T (n) = 2
n
T (n/2) + n
n
=⇒ Does not apply (a is not constant)
5. T (n) = 16T (n/4) + n =⇒ T (n) = Θ(n
2
) (Case 1)
6. T (n) = 2T (n/2) + n log n =⇒ T (n) = n log
2
n (Case 2)
7. T (n) = 2T (n/2) + n/ log n =⇒ Do e s not apply (non-polynomial difference between f (n) and n
log
b
a
)
8. T (n) = 2T (n/4) + n
0.51
=⇒ T (n) = Θ(n
0.51
) (Case 3)
9. T (n) = 0.5T (n/2) + 1/n =⇒ Does not apply (a < 1)
10. T (n) = 16T (n/4) + n! =⇒ T (n) = Θ(n!) (Case 3)
11. T (n) =
√
2T (n/2) + log n =⇒ T (n) = Θ(
√
n) (Case 1)
12. T (n) = 3T (n/ 2) + n =⇒ T (n) = Θ(n
lg 3
) (Case 1)
13. T (n) = 3T (n/ 3) +
√
n =⇒ T (n) = Θ(n) (Case 1)
14. T (n) = 4T (n/ 2) + cn =⇒ T (n) = Θ(n
2
) (Case 1)
15. T (n) = 3T (n/ 4) + n log n =⇒ T (n) = Θ(n log n) (Ca se 3)
16. T (n) = 3T (n/ 3) + n/2 =⇒ T (n) = Θ(n log n) (Case 2)
17. T (n) = 6T (n/ 3) + n
2
log n =⇒ T (n) = Θ(n
2
log n) (Case 3)
18. T (n) = 4T (n/ 2) + n/ log n =⇒ T (n) = Θ (n
2
) (Case 1)
19. T (n) = 64T (n/8) − n
2
log n =⇒ Does not apply (f (n) is not positive)
20. T (n) = 7T (n/ 3) + n
2
=⇒ T (n) = Θ(n
2
) (Case 3)
21. T (n) = 4T (n/ 2) + log n =⇒ T (n) = Θ(n
2
) (Case 1)
22. T (n) = T (n/ 2) + n(2 − cos n) =⇒ Does not apply. We are in Case 3, but the regularity condition is
violated. (Consider n = 2 πk, where k is odd and arbitrarily large. For any such choice of n, you can
show that c ≥ 3/2, thereby violating the re gularity condition.)
3
